home *** CD-ROM | disk | FTP | other *** search
/ PC World 2006 February / PCWorld_2006-02_cd.bin / software / vyzkuste / triky / triky.exe / httrack-3.33.exe / {app} / src / htshash.c < prev    next >
C/C++ Source or Header  |  2004-05-09  |  10KB  |  317 lines
  1. /* ------------------------------------------------------------ */
  2. /*
  3. HTTrack Website Copier, Offline Browser for Windows and Unix
  4. Copyright (C) Xavier Roche and other contributors
  5.  
  6. This program is free software; you can redistribute it and/or
  7. modify it under the terms of the GNU General Public License
  8. as published by the Free Software Foundation; either version 2
  9. of the License, or any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19.  
  20.  
  21. Important notes:
  22.  
  23. - We hereby ask people using this source NOT to use it in purpose of grabbing
  24. emails addresses, or collecting any other private information on persons.
  25. This would disgrace our work, and spoil the many hours we spent on it.
  26.  
  27.  
  28. Please visit our Website: http://www.httrack.com
  29. */
  30.  
  31.  
  32. /* ------------------------------------------------------------ */
  33. /* File: httrack.c subroutines:                                 */
  34. /*       hash table system (fast index)                         */
  35. /* Author: Xavier Roche                                         */
  36. /* ------------------------------------------------------------ */
  37.  
  38. /* Internal engine bytecode */
  39. #define HTS_INTERNAL_BYTECODE
  40.  
  41. #include "htshash.h"
  42.  
  43. /* specific definitions */
  44. #include "htsbase.h"
  45. #include "htsglobal.h"
  46. #include "htsmd5.h"
  47. /* END specific definitions */
  48.  
  49. /* Specific macros */
  50. #ifndef malloct
  51. #define malloct malloc
  52. #define freet free
  53. #define calloct calloc
  54. #define strcpybuff strcpy
  55. #endif
  56.  
  57. // GESTION DES TABLES DE HACHAGE
  58. // MΘthode α 2 clΘs (adr+fil), 2e cle facultative
  59. // hash[no_enregistrement][pos]->hash est un index dans le tableau gΘnΘral liens
  60. // #define HTS_HASH_SIZE 8191  (premier si possible!)
  61. // type: numero enregistrement - 0 est case insensitive (sav) 1 (adr+fil) 2 (former_adr+former_fil)
  62. #if HTS_HASH
  63. // recherche dans la table selon nom1,nom2 et le no d'enregistrement
  64. // retour: position ou -1 si non trouvΘ
  65. int hash_read(hash_struct* hash,char* nom1,char* nom2,int type,int normalized) {
  66.   char BIGSTK normfil_[HTS_URLMAXSIZE*2];
  67.   char* normfil;
  68.   char* normadr;
  69.   unsigned int cle;
  70.   int pos; 
  71.   // calculer la clΘ de recherche, non modulΘe
  72.   if (type)
  73.     cle = hash_cle(nom1,nom2);
  74.   else
  75.     cle = hash_cle(convtolower(nom1),nom2);         // case insensitive
  76.   // la position se calcule en modulant
  77.   pos = (int) (cle%HTS_HASH_SIZE);
  78.   // entrΘe trouvΘe?
  79.   if (hash->hash[type][pos] >= 0) {             // un ou plusieurs enregistrement(s) avec une telle clΘ existe..
  80.     // tester table de raccourcis (hash)
  81.     // pos est maintenant la position recherchΘe dans liens
  82.     pos = hash->hash[type][pos];
  83.     while (pos>=0) {              // parcourir la chaine
  84.       switch (type) {
  85.       case 0:         // sav
  86.         if (strfield2(nom1,hash->liens[pos]->sav)) {  // case insensitive
  87. #if DEBUG_HASH==2
  88.           printf("hash: found shortcut at %d\n",pos);
  89. #endif
  90.           return pos;
  91.         }
  92.         break;
  93.       case 1:         // adr+fil
  94.         {
  95.           if (!normalized)
  96.             normfil=hash->liens[pos]->fil;
  97.           else
  98.             normfil=fil_normalized(hash->liens[pos]->fil,normfil_);
  99.           if (!normalized)
  100.             normadr = jump_identification(hash->liens[pos]->adr);
  101.           else
  102.             normadr = jump_normalized(hash->liens[pos]->adr);
  103.           if ((strfield2(nom1,normadr)!=0) && (strcmp(nom2,normfil)==0)) {
  104. #if DEBUG_HASH==2
  105.             printf("hash: found shortcut at %d\n",pos);
  106. #endif
  107.             return pos;
  108.           }
  109.         }
  110.         break;
  111.       case 2:         // former_adr+former_fil
  112.         {
  113.           if (hash->liens[pos]->former_adr) {
  114.             if (!normalized)
  115.               normfil=hash->liens[pos]->former_fil;
  116.             else
  117.               normfil=fil_normalized(hash->liens[pos]->former_fil,normfil_);
  118.             if (!normalized)
  119.               normadr = jump_identification(hash->liens[pos]->former_adr);
  120.             else
  121.               normadr = jump_normalized(hash->liens[pos]->former_adr);
  122.             
  123.             if ((strfield2(nom1,normadr)!=0) && (strcmp(nom2,normfil)==0)) {
  124. #if DEBUG_HASH==2
  125.               printf("hash: found shortcut at %d\n",pos);
  126. #endif
  127.               return pos;
  128.             }
  129.           }
  130.         }
  131.         break;
  132.       }
  133.       // calculer prochaine position dans la chaine
  134.       {
  135.         int old=pos;
  136.         pos=hash->liens[pos]->hash_next[type];   // sinon prochain dans la chaine
  137.         if (old==pos)
  138.           pos=-1;         // erreur de bouclage (ne devrait pas arriver)
  139.       }
  140.     }
  141.     
  142.     // Ok va falloir chercher alors..
  143.     /*pos=hash->max_lien;    // commencer α max_lien
  144.     switch (type) {
  145.     case 0:         // sav
  146.       while(pos>=0) {
  147.         if (hash->liens[pos]->hash_sav == cle ) {
  148.           if (strcmp(nom1,hash->liens[pos]->sav)==0) {
  149.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  150. #if DEBUG_HASH==2
  151.             printf("hash: found long search at %d\n",pos);
  152. #endif
  153.             return pos;
  154.           }
  155.         }
  156.         pos--;
  157.       }
  158.       break;
  159.     case 1:         // adr+fil
  160.       while(pos>=0) {
  161.         if (hash->liens[pos]->hash_adrfil == cle ) {
  162.           if ((strcmp(nom1,hash->liens[pos]->adr)==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  163.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  164. #if DEBUG_HASH==2
  165.             printf("hash: found long search at %d\n",pos);
  166. #endif
  167.             return pos;
  168.           }
  169.         }
  170.         pos--;
  171.       }
  172.       break;
  173.     case 2:         // former_adr+former_fil
  174.       while(pos>=0) {
  175.         if (hash->liens[pos]->hash_fadrfil == cle ) {
  176.           if (hash->liens[pos]->former_adr)
  177.             if ((strcmp(nom1,hash->liens[pos]->former_adr)==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  178.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  179. #if DEBUG_HASH==2
  180.             printf("hash: found long search at %d\n",pos);
  181. #endif
  182.             return pos;
  183.           }
  184.         }
  185.         pos--;
  186.       }
  187.     }*/
  188. #if DEBUG_HASH==1
  189.     printf("hash: not found after test %s%s\n",nom1,nom2);
  190. #endif
  191.     return -1;    // non trouvΘ
  192.   } else {
  193. #if DEBUG_HASH==2
  194.     printf("hash: not found %s%s\n",nom1,nom2);
  195. #endif
  196.     return -1;    // non trouvΘ : clΘ non entrΘe (mΩme une fois)
  197.   }
  198. }
  199.  
  200. // enregistrement lien lpos dans les 3 tables hash1..3
  201. void hash_write(hash_struct* hash,int lpos,int normalized) {
  202.   char BIGSTK normfil_[HTS_URLMAXSIZE*2];
  203.   char* normfil;
  204.   unsigned int cle;
  205.   int pos; 
  206.   int* ptr;
  207.   //
  208.   if (hash->liens[lpos]) {                       // on sait jamais..
  209.     hash->max_lien = max(hash->max_lien,lpos);
  210. #if DEBUG_HASH
  211.     hashnumber=hash->max_lien;
  212. #endif
  213.     // ΘlΘment actuel sur -1 (fin de chaine)
  214.     hash->liens[lpos]->hash_next[0]=hash->liens[lpos]->hash_next[1]=hash->liens[lpos]->hash_next[2]=-1;
  215.     //
  216.     cle = hash_cle(convtolower(hash->liens[lpos]->sav),"");    // CASE INSENSITIVE
  217.     pos = (int) (cle%HTS_HASH_SIZE);
  218.     ptr = hash_calc_chaine(hash,0,pos);         // calculer adresse chaine
  219.     *ptr = lpos;                   // noter dernier enregistrΘ
  220. #if DEBUG_HASH==3
  221.     printf("[%d",pos);
  222. #endif
  223.     //
  224.     if (!normalized)
  225.       normfil=hash->liens[lpos]->fil;
  226.     else
  227.       normfil=fil_normalized(hash->liens[lpos]->fil,normfil_);
  228.     if (!normalized)
  229.       cle = hash_cle(jump_identification(hash->liens[lpos]->adr),normfil);
  230.     else
  231.       cle = hash_cle(jump_normalized(hash->liens[lpos]->adr),normfil);
  232.     pos = (int) (cle%HTS_HASH_SIZE);
  233.     ptr = hash_calc_chaine(hash,1,pos);         // calculer adresse chaine
  234.     *ptr = lpos;                   // noter dernier enregistrΘ
  235. #if DEBUG_HASH==3
  236.     printf(",%d",pos);
  237. #endif
  238.     //
  239.     if (hash->liens[lpos]->former_adr) {         // former_adr existe?
  240.       if (!normalized)
  241.         normfil=hash->liens[lpos]->former_fil;
  242.       else
  243.         normfil=fil_normalized(hash->liens[lpos]->former_fil,normfil_);
  244.       if (!normalized)
  245.         cle = hash_cle(jump_identification(hash->liens[lpos]->former_adr),normfil);
  246.       else
  247.         cle = hash_cle(jump_normalized(hash->liens[lpos]->former_adr),normfil);
  248.       pos = (int) (cle%HTS_HASH_SIZE);
  249.       ptr = hash_calc_chaine(hash,2,pos);         // calculer adresse chaine
  250.       *ptr = lpos;                   // noter dernier enregistrΘ
  251. #if DEBUG_HASH==3
  252.       printf(",%d",pos);
  253. #endif
  254.     }
  255. #if DEBUG_HASH==3
  256.     printf("] "); fflush(stdout);
  257. #endif
  258.   }
  259. #if DEBUT_HASH
  260.   else {
  261.     printf("* hash_write=0!!\n");
  262.     abortLogFmt("unexpected error in hash_write (pos=%d)" _ pos);
  263.     exit(1);
  264.   }
  265. #endif
  266.   //
  267. }
  268.  
  269. // calcul clΘ
  270. // il n'y a pas de formule de hashage universelle, celle-ci semble acceptable..
  271. unsigned long int hash_cle(char* nom1,char* nom2) {
  272.   /*
  273.   unsigned int sum=0;
  274.   int i=0;
  275.   while(*nom1) {
  276.     sum += 1;
  277.     sum += (unsigned int) *(nom1);
  278.     sum *= (unsigned int) *(nom1++);
  279.     sum += (unsigned int) i;
  280.     i++;
  281.   }
  282.   while(*nom2) {
  283.     sum += 1;
  284.     sum += (unsigned int) *(nom2);
  285.     sum *= (unsigned int) *(nom2++);
  286.     sum += (unsigned int) i;
  287.     i++;
  288.   }
  289.   */
  290.   return md5sum32(nom1)
  291.         +md5sum32(nom2);
  292. }
  293.  
  294. // calcul de la position finale dans la chaine des elements ayant la mΩme clΘ
  295. int* hash_calc_chaine(hash_struct* hash,int type,int pos) {
  296. #if DEBUG_HASH
  297.   int count=0;
  298. #endif
  299.   if (hash->hash[type][pos] == -1)
  300.     return &(hash->hash[type][pos]);    // premier ΘlΘment dans la chaine
  301.   pos=hash->hash[type][pos];
  302.   while(hash->liens[pos]->hash_next[type] != -1) {
  303.     pos = hash->liens[pos]->hash_next[type];
  304. #if DEBUG_HASH
  305.     count++;
  306. #endif
  307.   }
  308. #if DEBUG_HASH
  309.   count++;
  310.   longest_hash[type]=max(longest_hash[type],count);
  311. #endif
  312.   return &(hash->liens[pos]->hash_next[type]);
  313. }
  314. #endif
  315. // FIN GESTION DES TABLES DE HACHAGE
  316.  
  317.